class Solution
{
public:
    int rot[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
    int f = 0, min = 0;
    queue<pair<int, int>> que;
    int rotApple(vector<vector<int> >& grid)
    {
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] == 1) f++;
                else if (grid[i][j] == 2) que.push({ i,j });
            }
        }
        while (!que.empty())
        {
            int n = que.size();
            bool rotten = false;

            for (int i = 0; i < n; i++)
            {
                auto x = que.front();
                que.pop();
                for (auto cur : rot)
                {
                    int i = x.first + cur[0];
                    int j = x.second + cur[1];
                    if (i >= 0 && i < grid.size() && j >= 0 && j < grid[0].size() && grid[i][j] == 1)
                    {
                        grid[i][j] = 2;
                        que.push({ i,j });
                        f--;
                        rotten = true;
                    }
                }
            }
            if (rotten) min++;
        }
        return f ? -1 : min;
    }
};